#include<iostream>
#include<vector>
using namespace std;

class Solution
{
public:
bool searchMatrix(vector<vector<int>>& matrix,int target)
{
    int m = matrix.size();
    if (m == 0)
    {
        return false;
    }
    
    int n = matrix[0].size();
    int i = 0, j = n -1;

    while (i < m && j >= 0)
    {
        if(matrix[i][j] == target)
        {
            return true;
        }
        else if(matrix[i][j] > target)
        {
            --j;
        }else
        {
            ++i;
        }
    }
    return false;
}
};

int main()
{
    Solution s;
    vector<vector<int>> matrix;
    vector<int> a = {1,4,7,11,15};
    vector<int> b = {2,5,8,12,19};
    vector<int> c = {3,6,9,16,22};
    vector<int> d = {10,13,14,17,24};
    vector<int> e = {18,21,23,26,30};
    matrix.push_back(a);
    matrix.push_back(b);
    matrix.push_back(c);
    matrix.push_back(d);
    matrix.push_back(e);

    bool f = s.searchMatrix(matrix,21);
    cout <<  f << endl;
    return 0;
}
